package Heap;

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Queue;

public class Exercise {
    public static void main(String[] args) {
        int[] a=getLargestNumbers(new int[]{15,62,45,18,56},3);
        System.out.println(Arrays.toString(a));
    }
    //                                          top-k问题
    //求前k个最大/小的元素
    //堆的思路:1.求前k个最大的元素2.求前k个最小的元素
    //1.先将原数组中的前k个数组成一个小根堆，然后从k+1位置进行遍历，如果数组的值小于堆顶元素，那么就说明小根堆中的元素就是前k个元素中的最大值
    //如果数组中的元素大于堆顶元素(最小元素)，那么说明小根堆的元素不是前k个元素的最大值，这时把堆顶删除，插入大的元素，并且恢复成小根堆继续比较
    //2.先将原数组中的前k个数组成一个大根堆，如果有元素比堆顶元素还要大，那他肯定不是最小的
     //注意:前k大的元素中，第k大的元素就是堆顶的元素

    public static int[] getLeastNumbers(int[] arr, int k) {
        //   Arrays.sort(arr);
        //   int[] a=new int[k];
        //   for(int j=0;j < k;j++) {
        //     a[j]=arr[j];
        //   }
        //   return a;

        //堆
        if(arr==null||k==0) {
            return new int[0];
        }
        Queue<Integer> minHeap=new PriorityQueue<>(arr.length);   //给底层的数组开原数组大小的空间
        //O(N*logn)
        for(int x:arr) {
            minHeap.offer(x);
        }
        int[] a=new int[k];
        //O(k*logn)
        for(int i=0;i< k;i++) {
            a[i]=minHeap.poll();                        //小根堆的队头一定是所有元素里面最小的
        }
        return a;
    }
    public static int[] getLargestNumbers(int[] arr, int k) {
        //1.将数组中前k个元素放入到堆中，组成小根堆
        //2.将后面k-1个元素与堆顶元素进行比较，如果比堆顶元素小，往后比，如果比堆顶元素大，将原来的堆顶元素删除
        if(arr==null||k==0) {
            return new int[0];
        }
        Queue<Integer> minHeap=new PriorityQueue<>();
        //O(k*logk)
        int capacity=k;
        for (int x:arr) {
            if(capacity==0) {
                break;
            }
            minHeap.offer(x);
            capacity--;
        }
        //O(n-k)*logk
        for (int i = k; i < arr.length; i++) {
            int least=minHeap.peek();
            if(arr[i]>least) {
                minHeap.poll();
                minHeap.offer(arr[i]);
            }
        }
        int[] a=new int[minHeap.size()];
        for(int i=0;i<a.length;i++) {
            a[i]=minHeap.poll();
        }
        return a;
    }
}
